#include "binary_patterns.h"
#include "grate/util/compact_queue.h"

namespace growth_rate {
namespace binary_patterns {

static const size_t kMaxWordLength = 10000;

bool Pattern_4X_3Y::handle_xy_root(const Word &root, size_t xlen) {
  size_t xylen = root.length();
  size_t ylen = xylen - xlen;
  CHECK_GT(xlen, 0);
  CHECK_LT(xlen, xylen);
  uint8_t buffer[kMaxWordLength];
  size_t total_len = 3 * xylen + xlen;
  CHECK_LT(total_len, kMaxWordLength);
  Word word = build_xy_pattern(buffer, options_.pattern,
                               root.prefix(xlen), root.suffix(ylen));
  DCHECK_EQ(total_len, word.length());
  if (has_factor_forbidden_by_trie(word))
    return false;
  // Check if a factor has form xyxxyxy for some larger root length.
  for (size_t nxylen = xylen; 3 * nxylen + 1 < total_len; nxylen++) {
    for (size_t nxlen = 1; nxlen < nxylen; nxlen++) {
      size_t nlen = 3 * nxylen + nxlen;
      if (nlen >= total_len) break;
      for (size_t spos = 0; spos + nlen <= total_len; spos++) {
        if (is_xy_pattern(word.substr(spos, nlen), options_.pattern,
                          nxlen, nxylen - nxlen))
          return false;
      }
    }
  }
  if (avoid_xxx_) {
    // Check if there is a cubic factor for some larger root length.
    for (size_t rlen = xylen; 3 * rlen < total_len; rlen++) {
      size_t nlen = 3 * rlen;
      for (size_t spos = 0; spos + nlen <= total_len; spos++) {
        if (word.substr(spos, nlen).is_cube())
          return false;
      }
    }
  }
  CHECK(add_lexmin_word(word));
  return true;
}

bool Pattern_4X_3Y::handle_cubic_root(const Word &root) {
  uint8_t buffer[kMaxWordLength];
  size_t total_len = 3 * root.length();
  CHECK_LT(total_len, kMaxWordLength);
  Word word = build_xy_pattern(buffer, "xxx", root, /* unused */ root);
  DCHECK_EQ(total_len, word.length());

  if (has_factor_forbidden_by_trie(word))
    return false;

  CHECK(add_lexmin_word(word));
  return true;
}

bool Pattern_4X_3Y::construct() {
  uint8_t buffer[kMaxWordLength];

  if (avoid_xxx_)
    CHECK(add_lexmin_word("aaa"));

  IncreasingLengthWordQueue words_queue(options_.queue_capacity, 1);
  words_queue.push_word("aa");
  words_queue.push_word("ab");

  while (!words_queue.is_empty()) {
    Word root = words_queue.pop_word(buffer, kMaxWordLength);
    size_t xylen = root.length();
    if (avoid_xxx_)
      handle_cubic_root(root);
    for (size_t xlen = 1; xlen < xylen; xlen++)
      handle_xy_root(root, xlen);
    for (char letter = 'a'; letter <= 'b'; letter++) {
      if (can_extend_root(&root, letter)) {
        Word nroot = root.append(letter);
        words_queue.push_word(nroot);
      }
    }
    max_queue_size_ = Max(max_queue_size_, words_queue.get_size_in_bytes());
  }

  return true;
}

}  // namespace binary_patterns
}  // namespace growth_rate
